Plena grafeo

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj grafeo arbo subgrafeo ciklo kliko grado de vertico grado de grafeo Elektitaj klasoj de grafeoj plena grafeo plena dukolora grafeo kohera grafeo arbo grafeo dudividebla Fenda grafeo regula grafeo grafeo de Euler grafeo de Hamilton grafeo senrelifa pli... Grafeaj algoritmoj A* Bellman-Ford Dijkstry Fleury Floyd-Warshall Johnson Kruskal Prim traserĉado de grafeo – en larĝeco – en profundo plej proksima najbaro Problemoj prezentataj kiel grafeaj problemo de vojaĝisto problemo de ĉina leteristo problemo de marŝrutigado problemo de kunigado de geedzoj Aliaj kodo de Gray diagramo de Hasse kodo de Prüfer Reprezentado de grafeo Glosaro de grafeoteorio

vidi • diskuti • redakti

En grafeoteorio, plena grafeo estas simpla grafeo, en kiu ĉiun paron de malsamaj verticoj konektas eĝo.

La plena grafeo de n verticoj havas ${\displaystyle {\frac {n(n-1)}{2}}}$ eĝojn, kaj signiĝas per K_n. Ĝi estas regula grafeo de grado (n-1). Ĉiu plena grafeo estas kliko. Plenaj grafeoj estas maksimume koneksa ĉar la unusola vertica tranĉo kiu povas disigi la grafeon estas la tuta aro de verticoj.

Plena grafeo de n verticoj havas ${\displaystyle n!}$ aŭtomorfiojn kie la signo "!" signifas faktorialon.

Plena grafeo kun n verticoj prezentas la verticojn kaj eĝo de (n-1)-simplaĵo. Tiel K₃ respektivas al triangulo, K₄ respektivas al kvaredro, K₅ respektivas al kvinĉelo, kaj tiel plu.

K₁ ĝis K₄ estas ebenaj grafeo. Teoremo de Kuratowski asertas, ke ebena grafeo ne povas enhavi parton K₅ (aŭ la plenan dukoloran grafeon K_{3, 3}) kiel minoro. Pro tio ke K_n inkluzivas K_n-1, plena grafeo K_n kun n > 4 ne esta ebena.

K1: 0 lateroj	K2: 1 latero	K3: 3 lateroj	K4: 6 lateroj
K5: 10 lateroj	K6: 15 lateroj	K7: 21 lateroj	K8: 28 lateroj